Current trends in computing suggest that computers are becoming networked to one another on a greater and greater scale. For example, computers that previously were connected to other computers in the same building over a local-area network (LAN) are now commonly connected to other computers all over the world over a wide-area network (WAN), an intranet, or the Internet. The rising prominence of the Internet in fact presages a future where all computers are able to connect with one another over a single vast global network.
With this rise in connectivity comes the need for more prompt server responses to client download requests pertaining to directory services for such networks. One type of directory is similar to a phone book. The phone book permits a person to look up the phone number of another person so that the first person can communicate with the second person. Similarly, this type of directory for a computer network permits a computer user to look up the electronic address of another computer user (for example, the user's current dynamic Internet Protocol (IP) address in the case of a typical home Internet user), so that the first user can communicate with the second user. Although directory services may be used for a wide variety of different applications other than just to locate a user by looking up his or her electronic address, such user-location applications are nevertheless very common. For example, being able to determine the current IP address of a computer user is a very important feature for such diverse Internet applications as Internet telephony, whiteboarding, and videoconferencing.
However, unlike the phone book, which is a static directory, the directory for a computer network such as the Internet frequently must be dynamic in order to be useful. The phone book is a static directory in that it is not updated very often, typically only once a year when a new book is published. The phone book remains accurate, however, because each person's phone number generally also does not change very often. Conversely, in the case of the Internet, while every user may have a static electronic mail address (that is, an e-mail address that does not change often), every user typically does not have a static IP address. Dial-up users in particular are assigned a dynamic IP address by their Internet Service Provider (ISP) each time they initiate an online session. This lessens the accuracy and usefulness of a static directory for many Internet applications.
Static directory services nevertheless do exist for the Internet, and other Internet-like networks. One such static directory service is provided by the Lightweight Directory Access Protocol (LDAP). The LDAP is known within the art, and is specifically described in W. Yeong, et al., Request for Comments (RFC) 1777, March 1995, which is hereby incorporated by reference. The LDAP permits a server to maintain a static directory. Clients capable of communicating with the server are able to add entries to the directory by sending the server the appropriate request. These entries are static in that they persist until the client establishing them requests their removal from the server. If clients forget to make such requests, the server may maintain their entries in the directory indefinitely, which in time may result in the directory including outdated information. For example, if the server is maintaining a user-location directory of IP addresses, an entry containing the dynamic IP address of a client who has since logged off the Internet is inaccurate.
Dynamic directory services differ from static directory services in that entries must be periodically refreshed by their clients, or otherwise they automatically are removed by the server. Dynamic directory services also exist for the Internet, and other Internet-like networks. One such dynamic directory service is provided by the User Location Service (ULS). The ULS is known within the art, and is specifically described in R. Williams, Internet Draft "draft-uls-1.txt", February 1996, which is hereby incorporated by reference. A server maintaining a dynamic directory as provided by the ULS is receptive to requests from clients to add entries to the directory that include a time-to-live value set by the client. If the client does not refresh its entry before the time-to-live value times out, the server is permitted to delete the entry. The time-to-live value is also known as the client refresh period. Thus, if the server is maintaining a user-location directory of IP addresses, an entry containing the dynamic IP address of a client who has since logged off will eventually be deleted by the server.
Another dynamic directory service is an extension to the LDAP as described in the U.S. patent application entitled "Server-Determined Client Refresh Periods for Dynamic Directory Services," filed on Jul. 2, 1997, Ser. No. 08/886,796, which is hereby incorporated by reference, now U.S. Pat. No. 6,016,508. The dynamic directory service provided by this reference extends the capability of an LDAP directory to include dynamic entries. Thus, when a client sends a request to a server to create an entry for an LDAP directory maintained by the server, the client is able to specify whether the entry to be created is dynamic or static. If the entry is dynamic, the client must immediately send a refresh request to the server, in response to which the client will receive a response including a client-refresh period. If the client does not send another refresh request prior to the timing out of this period, the entry will eventually be deleted by the server.
Dynamic directories are useful in that they permit the servers maintaining them to periodically perform a garbage collection operation in a manner which does not affect the directories' accuracy. An entry in a dynamic directory is dynamic in that it lives for only a given period of time unless refreshed by its client. The server thus only deletes expired entries. By comparison, servers maintaining static directories perform garbage collections indiscriminately, because they do not know which entries have expired. The servers may delete only very old entries, which probably are outdated, but this means the entries will have persisted long enough to have rendered the directories inaccurate for a period of time. Alternatively, the servers may delete relatively younger entries, in which case the accuracy of the directory is maintained but some accurate entries will likely have been deleted.
Dynamic directories have their own flaws, however. Because the directories are dynamic, clients typically are constantly logging onto and off servers maintaining such dynamic directories. A particular client may wish to determine the identity of the other clients (i.e., their IP addresses) currently logged onto the server. The particular client may wish to do this so that it may initiate a video conference with one of the other clients, for example, or an Internet telephone call. The particular client therefore submits a directory download request to the server, the request including a particular directory filter indicating the type of clients that this particular client is interested in knowing whether they are also logged onto the server. For example, the directory filter may indicate that the particular client is interested in obtaining the IP addresses for all clients having corresponding user information reflecting that they are from the state of Washington. As another example, the directory filter may indicate that the particular client is interested in the IP addresses for all clients have corresponding user information reflecting that they have videoconferencing capability.
Processing these directory download requests, however, is typically very time consuming for the server. The server is first required to traverse the entire dynamic directory database, then filter out the information the particular client is not interested in, and finally represent the collected information in a particular protocol format for submission back to the client. For many Internet-related dynamic directory services, such as ULS and Internet Locator Service (ILS), the directory is represented by a tree data structure, which is especially time consuming for the server to traverse. This problem is compounded by the fact that in Internet-related dynamic directory services, the potential for thousands of clients or more to be logged on at any one time exists, with the potential for hundreds of clients logging onto or logging off of the server at any one moment existing as well. Thus, by the time the server traverses the dynamic directory to process a directory download request, the information may quickly become out-of-date.
Because of the time-consuming nature of the directory download requests in terms of processing them at the server, many such requests may become backed up in a queue awaiting to be serviced by the server. Eventually, the queue may become full, and the server may become unresponsive to the requests. In queuing theory, this is considered a classic mishap--that is, when the service rate of requests at the server is less than the arrival rate of new requests to the server. In addition, directory download requests may block log-on and log-off requests from other clients (although log-on and log-off requests may block directory download requests as well). Thus, as the server attempts to process the directory download requests, the entire dynamic directory maintained by the server may slow down. Clients attempting to log on and log off the server may find that it is difficult at best to do so. Clients submitting new directory download requests to the server may find that their requests are not serviced in a reasonable amount of time. The dynamic directory itself may become gridlocked, and slow to a halt, as a result of excessive directory download requests received by the server.
There is a need, therefore, to solve these problems related to directory download requests. Such a solution should permit a server to more quickly service directory download requests received from clients logged onto the server. More specifically, such a solution should permit the server to quickly service the requests so that the dynamic directory service maintained by the server does not become incapacitated as a result of such download requests.